/**
 * 
 */
package logic.huffman;

import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Set;


import datamodel.huffman.tree.Tree;
import datamodel.RGB;

/**
 * Implements the Huffman algorithm for an image.
 * 
 * @author Kevin Munk, Jakob Karolus, Magnus Brand
 * @version 1.0
 * 
 */
public class HuffmanTree {
	

	/**
	 * returns a HuffmanTree which is based on the given file (an image)<br>
	 * Less "weighted"(less probability) subtrees will be placed right.
	 * 
	 * @param file the file to load and generate the tree
	 * @return the Huffman tree for the file
	 * @throws FileNotFoundException
	 * @throws IOException
	 */
	public static Tree getHuffmanTree(String file) throws FileNotFoundException, IOException{
		// Iterate over image and remember how often they occur
		io.ImageReader ireader = new io.ImageReader(file);
		Iterator<RGB> iIterator = ireader.iterator();
		// this map stores one color (RGB) as a tree (with one node) and its frequency in the picture 
		HashMap<Tree, Integer> colorFreqs = new HashMap<Tree, Integer>();
		while(iIterator.hasNext()) {
			// freq=1 for previously non-existant RGB
			RGB col = iIterator.next();
			Tree t = new Tree();
			t.setCurrentNode(new Tree.Node(col));
			// containsKey() uses hashCode(), not equals(). Trees must implement that
			if(!colorFreqs.containsKey(t)) {
				colorFreqs.put(t, 1);
			}
			else {
				// increment for existing RGB
				int freqOfCol = colorFreqs.get(t);
				++freqOfCol;
				colorFreqs.put(t, freqOfCol);
			}
		}
		
		if(colorFreqs.size() == 0) // empty pic
			return new Tree(); // empty tree
		
		// Merge until only one tree is left. This is the Huffman tree
		while(colorFreqs.size() > 1) {
			// pick two RGBs with the smallest frequencies; every call also deletes the returned entry from the map
			Entry<Tree, Integer> e1 = takeEntryWithSmallestFreq(colorFreqs),
				 				 e2 = takeEntryWithSmallestFreq(colorFreqs);
			Tree t1 = e1.getKey(),
				 t2 = e2.getKey();
			
			// Merge into one tree with freq = freq(t1) + freq(t2)
			Tree t = new Tree();
			t.setCurrentNode(new Tree.Node(null));
			
			t.setLeftNode(t2.getCurrentNode());
			t.moveToLeftNode();
			copySubtree(t, t2);
			
			// t1 has smaller probability (guaranteed by order of calls to takeTreeWithSmall...) -> goes right
			t.setRightNode(t1.getCurrentNode());
			t.moveToRightNode();
			copySubtree(t, t1);
			
			colorFreqs.put(t, e1.getValue() + e2.getValue());
		}
		
		// return the remaining tree
		return colorFreqs.keySet().toArray(new Tree[0])[0];
	}

	// SequentialTrees can't just be moved; they need to be copied.
	private static void copySubtree(Tree t, Tree subtree) {
		if(subtree.hasLeftNode()) {
			subtree.moveToLeftNode();
			t.setLeftNode(subtree.getCurrentNode());
			t.moveToLeftNode();
			copySubtree(t, subtree);
		}
		if(subtree.hasRightNode()) {
			subtree.moveToRightNode();
			t.setRightNode(subtree.getCurrentNode());
			t.moveToRightNode();
			copySubtree(t, subtree);
		}
		subtree.moveToParentNode(); // this will fail for the first call in the recursive call hierarchy; no problem however
		t.moveToParentNode();
			
		
	}

	private static Entry<Tree, Integer> takeEntryWithSmallestFreq(HashMap<Tree, Integer> frequencies) {
		Set<Entry<Tree,Integer>> s = frequencies.entrySet();
		Entry<Tree, Integer> entryWithSmallestFreq = null;
		for(Entry<Tree, Integer> e : s) {
			// in first iteration
			if(entryWithSmallestFreq == null)
				entryWithSmallestFreq = e;
			else {
				if((Integer)e.getValue() < (Integer)entryWithSmallestFreq.getValue())
					entryWithSmallestFreq = e;
			}	
		}
		frequencies.remove(entryWithSmallestFreq.getKey());
		return entryWithSmallestFreq;
	}

}
